//
// Created by ASUS on 2023/9/21.
//
/*
 *
给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。
一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
收集距离当前节点距离为 2 以内的所有金币，或者
移动到树中一个相邻节点。
你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
如果你多次经过一条边，每一次经过都会给答案加一。

示例一：
 输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。

 示例二：
 输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出：2
解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。

 提示：
n == coins.length
1 <= n <= 3 * 104
0 <= coins[i] <= 1
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵合法的树。
 */

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
	int collectTheCoins(vector<int> &coins, vector<vector<int>> &edges) {
		int n = coins.size();
		vector<vector<int>> g(n);
		vector<int> deg(n);
		for (auto &e: edges) {
			int x = e[0], y = e[1];
			g[x].push_back(y);
			g[y].push_back(x); // 建图
			deg[x]++;
			deg[y]++; // 统计每个节点的度数（邻居个数）
		}

		int left_edges = n - 1; // 剩余边数
		// 拓扑排序，去掉没有金币的子树
		vector<int> q;
		for (int i = 0; i < n; i++)
			if (deg[i] == 1 && coins[i] == 0) // 没有金币的叶子
				q.push_back(i);
		while (!q.empty()) {
			left_edges--; // 删除节点 x（到其父节点的边）
			int x = q.back(); q.pop_back();
			for (int y: g[x])
				if (--deg[y] == 1 && coins[y] == 0) // 没有金币的叶子
					q.push_back(y);
		}

		// 再次拓扑排序
		for (int i = 0; i < n; i++)
			if (deg[i] == 1 && coins[i]) // 有金币的叶子（判断 coins[i] 是避免把没有金币的叶子也算进来）
				q.push_back(i);
		left_edges -= q.size(); // 删除所有叶子（到其父节点的边）
		for (int x: q) // 遍历所有叶子
			for (int y: g[x])
				if (--deg[y] == 1) // y 现在是叶子了
					left_edges--; // 删除 y（到其父节点的边）
		return max(left_edges * 2, 0);
	}
};

/*
提示 1
定义一个点的度数为其邻居个数。如果一个点的度数为 1，那么这个点叫做叶子节点，例如示例 2 的 3,4,6,7 都是叶子节点。
如果叶子节点没有金币，我们有必要移动到叶子节点吗？没有必要。
那么可以先把这些没有金币的叶子节点去掉。如果去掉后又产生了新的没有金币的叶子节点，就继续去掉。
怎么实现？拓扑排序。一开始，把没有金币的叶子节点都加到队列中。然后不断循环直到队列为空。每次循环，弹出队首的节点 x，并删除 x 及其邻居之间的边。我们并不需要实际删除边，只需要把邻居的度数减少 1。如果一个邻居的度数减少为 1 且没有金币，就加到队列中，继续拓扑排序。
提示 2
看示例 2，在去掉节点 6 之后，现在每个叶子节点上都有金币。
由于可以「收集距离当前节点距离为 2 以内的所有金币」，我们没有必要移动到叶子节点再收集，而是移动到叶子节点的父节点的父节点，就能收集到叶子节点上的金币。
那么，去掉所有叶子，然后再去掉新产生的叶子，剩余节点就是必须要访问的节点。
提示 3
由于题目要求最后回到出发点，无论从哪个点出发，每条边都必须走两次。这是因为把出发点作为树根，递归遍历这棵树，那么往下「递」是一次，往上「归」又是一次，每条边都会经过两次。
所以答案就是剩余边数乘 222。当我们删除节点时，也可以看成是删除这个点到其父节点的边。
特别地，如果所有点都要被删除，那么当剩下两个点时，这两个点之间的边我们会删除两次，这会导致剩余边数等于 -1，而此时答案应该是 0。所以最后答案要和 0 取最大值。
代码实现时，由于我们不需要得到一个严格的拓扑序，所以简单地用栈或者数组代替队列，也是可以的。
 */